#include "findstring.h"
#include <list>
#include <string>
#include <vector>
#include <stdexcept>
using namespace std;

list<string::const_iterator> FindString(const string &str, const string &subString)
{
	return FindStringKMP(str, subString);
}

list<string::const_iterator> FindStringTrivial(const string &str, const string &subString)
{
    if (subString.empty())
        throw logic_error("empty substring");
    list<string::const_iterator> result;
    for(string::const_iterator i = str.begin(); i != str.end(); ++i)
    {
        bool flag = true;
        string::const_iterator j = subString.begin();
        for (string::const_iterator k = i;
             flag && j != subString.end() && k != str.end(); ++j, ++k)
        {
            flag = *j == *k;
        }
        if (flag && j == subString.end())
        {
            result.push_back(i);
        }
    }

    return result;
}

list<string::const_iterator> FindStringKMP2(const string &str, const string &subString)
{
    list<string::const_iterator> res;
    if (subString.empty())
        throw logic_error("empty substring");
    vector<int> pf (subString.length());

    pf[0] = 0;
    for (int k = 0, i = 1; i<subString.length(); ++i){
        while(k>0 && subString[i] != subString[k])
            k = pf[k-1];

        if (subString[i] == subString[k])
            k++;

        pf[i] = k;
    }

    for (int k = 0, i = 0; i<str.length(); ++i){
        while ((k>0) && (subString[k] != str[i]))
            k = pf[k-1];

        if (subString[k] == str[i])
            k++;

        if (k==subString.length())
        {
            res.push_back(str.begin() + i-subString.length()+1);
        }
    }

    return res;
}


vector<size_t> ComputePrefixFunction(const string &s)
{
	if (s.empty())
		return vector<size_t>();
	vector<size_t> result(s.length());
	size_t m = s.length();
	size_t k = 0;
	for (size_t q = 2; q <= m; ++q)
	{
		for (; k > 0 && s[k + 1 - 1] != s[q - 1]; k = result[k - 1]);

		if (s[k + 1 - 1] == s[q - 1])
		{
			k = k + 1;
		}
		result[q - 1] = k;
	}
	return result;
}

list<string::const_iterator> FindStringKMP(const string &str, const string &subString)
{
    if (subString.empty())
    {
        throw logic_error("empty substring");
    }
	list<string::const_iterator> result;
	size_t n = str.length();
	size_t m = subString.length();
	vector<size_t> pi = ComputePrefixFunction(subString);
	size_t q = 0;
    for (size_t i = 1; i <= n; ++i)
	{
		for (; q > 0 && subString[q + 1 - 1] != str[i - 1]; q = pi[q - 1]);

		if (subString[q + 1 - 1] == str[i - 1])
		{
			++q;
		}

		if (q == m)
		{
			result.push_back(str.begin() + i - m);
			q = pi[q - 1];
		}

	}

	return result;
}
